/*
 *  Copyright 2007-2008 by Matthias Buch-Kromann <mbk.isv@cbs.dk>.
 *  
 *  This file is part of the Open-source Dependency Toolkit (OSDT),
 *  see http://code.google.com/p/open-source-dependency-toolkit.
 *  
 *  The OSDT is free software: you can redistribute it and/or modify
 *  it under the terms of the GNU Lesser General Public License as 
 *  published by the Free Software Foundation, either version 3 of 
 *  the License, or (at your option) any later version.
 * 
 *  The OSDT is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU Lesser General Public License for more details.
 * 
 *  You should have received a copy of the GNU Lesser General Public 
 *  License along with the OSDT in the files COPYING and COPYING.LESSER.
 *  If not, see http://www.gnu.org/licenses.
 */

package org.osdtsystem.graphs.views;

import org.osdtsystem.exceptions.IllegalCycleException;
import org.osdtsystem.exceptions.NodeNotFoundException;
import java.util.List;
import java.util.Set;
import org.osdtsystem.exceptions.IllegalRelationException;
import org.osdtsystem.exceptions.IllegalOrderException;
import org.osdtsystem.values.EdgeID;
import org.osdtsystem.values.Feature;
import org.osdtsystem.values.NodeID;

/**
 *
 * @author Matthias Buch-Kromann <mbk.isv@cbs.dk>
 */
public interface DependencyTree extends Tree {
    // Construction methods
    /**
     * Add a feature to the list of permitted edge features for the 
     * dependency tree.
     * @param feature the new edge feature
     */
    public void addDependencyFeature(Feature feature);

    /**
     * Specify the set of known complement relations. Any dependency relation
     * that is not contained in this set is assumed to be an adjunct relation. 
     * @param complementRelations the set of complement relations
     */
    public void setComplementRelations(Set<Object> complementRelations);

    /**
     * Specify the set of known complement relations. Any dependency relation
     * that is not contained in this set is assumed to be an adjunct relation. 
     * @param adjunctRelations the set of complement relations
     */
    public void setAdjunctRelations(Set<Object> adjunctRelations);

    /**
     * Specify the new governor of a given node, and the dependency relation. 
     * The operation is not performed if it results in a cycle (ie, a non-tree). 
     * In this case, an exception is thrown instead.
     * @param node the node
     * @param governor the new governor
     * @param relation the dependency relation
     * @return the new edge
     * @throws NodeNotFoundException if one of the nodes is non-existent
     * @throws IllegalCycleException if the operation results in a cyclic graph
     * @throws IllegalOrderException
     * @throws IllegalRelationException 
     */
    public EdgeID setGovernor(NodeID node, NodeID governor, Object relation)
            throws NodeNotFoundException, IllegalCycleException,
                IllegalOrderException, IllegalRelationException;
    
    /**
     * Add a new dependent node to the given governor  with the given dependency relation. 
     * @param governor the parent node
     * @param relation the edge relation
     * @return the new node
     * @throws NodeNotFoundException if the parent node is not in the tree
     * @throws IllegalRelationException
     * @throws IllegalOrderException 
     */
    @Override
    public NodeID addNode(NodeID governor, Object relation)
            throws NodeNotFoundException, IllegalRelationException, IllegalOrderException;
    
    // Query methods    
    /**
     * The edges in the tree.
     * @return the list of edges in the tree
     */
    public List<EdgeID> dependencies();
    
    /**
     * The parent edge connecting a node with its parent.
     * @param node the node
     * @return the edge from the node's parent to the node
     */
    public EdgeID governorEdge(NodeID node);
    
    /**
     * The child edges connecting a node with its children.
     * @param node the node
     * @return the list of all child edges
     */
    public List<EdgeID> dependentEdges(NodeID node);

    /**
     * Return all dependency edges from the node to its complements in the given graph.
     * @param node the node
     * @return the list of all complement edges
     */
    public List<EdgeID> complementEdges(NodeID node);
    
    /**
     * Return all dependents of the node in the tree.
     * @param node the node
     * @return the list of dependent nodes
     */
    public List<NodeID> dependents(NodeID node);
    
    /**
     * Return all complements of the node in the tree.
     * @param node the node
     * @return the list of complement nodes
     */
    public List<NodeID> complements(NodeID node);
    
    /**
     * Return all adjuncts of the node in the tree.
     * @param node the node
     * @return the list of adjunct nodes
     */
    public List<NodeID> adjuncts(NodeID node);
    
    
    /**
     * Return the governor of the node in the tree.
     * @param node the node
     * @return its governor node
     */
    public NodeID governor(NodeID node);
    
    /**
     * Return all dependency edges from the node to its adjuncts in the given graph.
     * @param node the node
     * @return the list of all adjunct edges
     */
    public List<EdgeID> adjunctEdges(NodeID node);
    
   /**
     * The lowest node in the tree that dominates two given nodes 
     * (the <i>lattice join</i>). 
     * @param node1 the first node
     * @param node2 the second node
     * @return the join of the two nodes
     * @throws NodeNotFoundException
     */
    public NodeID dependencyJoin(NodeID node1, NodeID node2) 
            throws NodeNotFoundException;

    /**
     * The two paths from <code>node1</code> and <code>node2</code> respectively 
     * to the join of the two nodes in the tree. The path from a node to its join
     * with the other node is empty if the node coincides with the join. 
     * @param node1 the first node
     * @param node2 the second node
     * @return a list containing the two paths from <code>node1</code> and
     * <code>node2</code> respectively to their join.
     * @throws NodeNotFoundException if one of the two nodes doesn't exist in the tree
     */
    public List<List<EdgeID>> dependencyJoinPaths(NodeID node1, NodeID node2)
            throws NodeNotFoundException;
    
    /**
     * The parent node of the given edge.
     * @param edge the edge
     * @return the parent node
     */
    public NodeID governor(EdgeID edge);

    /**
     * The child node of the given edge.
     * @param edge the edge
     * @return the child node
     */
    public NodeID dependent(EdgeID edge);    
    
    /**
     * Is the edge a complement edge in the given graph? The value is undefined
     * if the edge is not contained in the graph. 
     * @param edge the edge
     * @return <code>true</code> if the edge is a complement edge, <code>false</code>
     * otherwise.
     */
    public boolean isComplement(EdgeID edge);

    /**
     * Is the edge an adjunct edge in the given graph? The value is undefined
     * if the edge is not contained in the graph.
     * @param edge the edge
     * @return <code>true</code> if the edge is an adjunct edge, <code>false</code>
     * otherwise.
     */
    public boolean isAdjunct(EdgeID edge);
}
